package com.gqb.tree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeBaseOnLink {
	private class Node{
		
		private Node leftNode;
		private Node rightNode;
		private String data;
		public Node(String data) {
			super();
			this.data = data;
		}
		public Node getLeftNode() {
			return leftNode;
		}
		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}
		public Node getRightNode() {
			return rightNode;
		}
		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}
		public String getData() {
			return data;
		}
		public void setData(String data) {
			this.data = data;
		}
	}
	
	private Node root;
	private int nodeCount;
	public BinaryTreeBaseOnLink(String root) {
		super();
		this.root = new Node(root);
		nodeCount++;
	}
	
	public boolean addLeft(String parent,String sonLeft){
		Node parentNode=getNode(root, parent);
		if(parentNode!=null){
			parentNode.leftNode=new Node(sonLeft);
			return true;
		}
		return false;
		
	}
	
	public boolean addRight(String parent,String sonRight){
		Node parenNode=getNode(root, sonRight);
		if(parenNode!=null){
			parenNode.rightNode=new Node(sonRight);
			return true;
		}
		return false;
	}
	/**
	 * 中序遍历
	 * @param rootNode
	 * @param data
	 * @return
	 */
	private Node getNode(Node rootNode,String data){
		if(rootNode==null){
			System.out.println("树还未初始化");
			return null;
		}
		if(rootNode.getData().equals(data))
			return rootNode;
		Node node=null;
		if(rootNode.leftNode!=null){
			if(rootNode.leftNode.getData().equals(data))
			{
				node=rootNode.leftNode;
			}else {
				node=getNode(rootNode.leftNode, data);
			}
		}
		
		if(node==null&&rootNode.rightNode!=null){
			if(node.rightNode.getData().equals(data))
			{
				return node.getRightNode();
			}else{
				node=getNode(node.getRightNode(), data);
			}
		}
		return node;
	}
	
	public List<Node> Children(String parent){
		List<Node> nodes=new ArrayList<BinaryTreeBaseOnLink.Node>();
		Node parentNode=getNode(root, parent);
		nodes.add(parentNode.getLeftNode());
		nodes.add(parentNode.getRightNode());
		return nodes;
	}
	
	public int depth(Node root,int deep){
		int templ=0,tempr=0;
		int depth=0;
		if(root.leftNode!=null){
			templ=depth(root.leftNode,deep+1);
		}
		if(templ>depth)
			depth=templ;
		if(root.rightNode!=null){
			tempr=depth(root.rightNode, deep+1);
		}
		if(tempr>depth)
			depth=tempr;
		return deep>depth?deep:depth;
	}
	
	public static void main(String[] args) {
		BinaryTreeBaseOnLink tree=new BinaryTreeBaseOnLink("A");
		tree.addLeft("A", "B");
		tree.addRight("A", "C");
		tree.addLeft("B", "D");
		tree.addRight("B", "E");
		tree.addLeft("C", "F");
		tree.addLeft("D", "H");
		tree.addLeft("H", "R");
		System.out.println(tree.Children("A").size());
		System.out.println("树的深度为"+tree.depth(tree.root, 1));
	}
	
}
